Diagramming software is used to produce graphical diagrams on a digital workspace or canvas. Typically, there are shapes or objects in a workspace, and a user can choose to connect any two shapes with a connector. It is desirable for the connector to be as short as possible while avoiding other shapes (known as obstacles) that are not a source shape (where the connector begins) or a target shape (where the connector terminates). The process of finding the shortest path while avoiding the obstacles is known as routing the connector.
It is also desirable to have good visual feedback as the user is dragging the termination point of the connector as to where the final position of the connector will be located. Current applications do not perform this feedback very well because there is a lag in the visual feedback due to computations being performed by the system. By way of example, in some diagramming applications the connector will jump quite a bit while the use is dragging the connector.
In addition, often the shortest path between the source shape and target shape that avoids obstacles is not a smooth path. However, it is desirable for the user that the connector has a smooth path without sharp edges and abrupt turns. From an aesthetic standpoint, the connector that has a smooth or flowing path will look more pleasing to the user.
Moreover, a tangent visibility graph is often used to find the shortest path. However, a tangent visibility graph can be quite large and require extended computation times. For example, there might be 4n2 edges in the tangent visibility graph of n shapes. Even for a small n, to calculate the tangent visibility graph can take several seconds. For an interactive scenario, this is unacceptable, as there is a lag time between when the user moves the pointing device and when the user sees the visual feedback. This lag time makes users feel quite uncomfortable.